#include <iostream>
#include <algorithm>
#include <queue>
#include <utility>
#include <vector>
#include <fstream>

std::ifstream fin("bfdiff.in");
std::ifstream fin2("bfdiff.out1");

int const inf = 1<<25;
int const maxn = 200;
int n, m;
int dist[maxn];

struct node
{
	int to;
	int cost;
};

void add_edge(std::vector<std::vector<node> > & graph, int x, int y, int c)
{
	graph[x].push_back({y, c});
}

int dijkstra(std::vector<std::vector<node> > & graph, int source, int target)
{
	int v = graph.size();
//	bool visited[v];
//	fill(visited, visited+v, false);
	std::fill(dist, dist+v, inf);
	dist[source] = 0;
	typedef std::pair<int, int> end_cost;
	struct cmp
	{
		bool operator()(const end_cost & a, const end_cost & b) { return a.second > b.second; }
	};
	std::priority_queue<end_cost, std::vector<end_cost>, cmp> pq;
	pq.push(std::make_pair(source, 0));
	while (!pq.empty()) {
		end_cost tmp = pq.top();
		pq.pop();
		int u = tmp.first;
		if (dist[u] < tmp.second) continue;
	//	if (visited[u]) continue;
	//	visited[u] = true;
		for (std::vector<node>::iterator edge = graph[u].begin();
		 		edge != graph[u].end(); edge++) {
			if (dist[(*edge).to] > dist[u] + (*edge).cost) {
				dist[(*edge).to] = dist[u] + (*edge).cost;
				pq.push(std::make_pair((*edge).to, dist[(*edge).to]));
			}
		}
	}
	return dist[target];
}

bool judge_singlet()
{
	int i = 1;
	for (; i < n; i++)
		if (dist[i] <= dist[i-1]) break;
	if (i == n) return false;
	for (; i < n; i++)
		if (dist[i] >= dist[i-1]) break;
	return (i == n);
}

bool judge_mono()
{
	int i = 1;
	for (; i < n; i++)
		if (dist[i] <= dist[i-1]) return false;
	return i == n;
}

int main()
{
	int T; fin >> T;
	while (T--) {
		fin >> n >> m;

		std::vector<std::vector<node> > graph;
		graph.resize(n);
		for (int i = 0; i < m; i++) {
			int x, y, cost;
			fin >> x >> y;
			fin2 >> cost;
			std::cout << cost << '\n';

			x--; y--;
			add_edge(graph, x, y, cost);
			add_edge(graph, y, x, cost);
		}
		dijkstra(graph, 0, n-1);

		if (!(judge_mono() || judge_singlet()))
			std::cout << "fuck\n";
	}
}

